package com.bascker.algorithm.practice.arr.easy.maximum_product;

import java.util.Objects;

/**
 * 三个数的最大乘积: 给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
 *
 * For example:
 *  in: [1,2,3],    out: 6
 *  in: [1,2,3,4]   out: 24
 *
 * Note:
 *  1) 给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
 *  2) 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围
 *
 * @author bascker
 * @apiNote from leetcode T628
 */
public class Solution {

    public int maximumProduct(int[] nums) {
        if (Objects.isNull(nums) || nums.length < 3) {
            return 0;
        }

        // 线性扫描：找到最大的3个数、最小的 2 个数(因为最小的2个数可能都是负数，负负得正)，一次遍历
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        for (int x : nums) {
            if (x >= max1) {
                // 换位置: 第1大的变为第3大值，第1大的变为第2大值，第1大值为 x
                max3 = max2;
                max2 = max1;
                max1 = x;
            } else if (x >= max2) {
                max3 = max2;
                max2 = x;
            } else if (x >= max3) {
                max3 = x;
            }

            if (x <= min1) {
                // 换位置: 最小值的变为第2小值，最小值为 x
                min2 = min1;
                min1 = x;
            } else if(x <= min2) {
                min2 = x;
            }
        }

        return Math.max(max1 * max2 * max3, max1 * min1 * min2);
    }

}
